package leecode

func lengthOfLIS(nums []int) int {
	result := 1
	dp := make([]int, len(nums)) //以nums[i] 结尾的最长递增子序列
	//初始化dp数组
	for i := 0; i < len(dp); i++ {
		dp[i] = 1
	}
	for i := 1; i < len(nums); i++ {
		//以nums[i] 结尾的最长递增子序列
		temp := 0
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				temp = max(temp, dp[j])
				dp[i] = temp + 1
			}
		}
		result = max(result, dp[i])
	}
	return result
}
